package Mydwei;

import java.util.Comparator;
import java.util.PriorityQueue;

class zhuandadui implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
}
//一般从小到大排列k个建大堆，从大到小排k个建小堆;
public class Test2 {
    public static int[] topk(int[] arr,int k) {  //找前k个最大的元素 1 :数据小全部建成大堆然后取前k个;
        zhuandadui zhuandadui=new zhuandadui();
        PriorityQueue<Integer> priorityQueue =new PriorityQueue<>(zhuandadui);
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }
        int[]ret =new int[k];
        for (int i = 0; i <k; i++) {
            int val=priorityQueue.poll();
            ret[i]=val;
        }
        return ret;
    }
    public static int[] topk2(int[] arr,int k) {  //找前k个最大的元素 2 :数据大时建成有k个数据小堆然后与后面依次比较;
        zhuandadui zhuandadui=new zhuandadui();
        PriorityQueue<Integer> priorityQueue =new PriorityQueue<>(k,zhuandadui);//拥有k个元素的堆
        if(k<=0){
            return  new int[0];
        }
        for (int i = 0; i < arr.length; i++) {
            if(priorityQueue.size()<k){
                priorityQueue.offer(arr[i]);//先入k个建成堆;
            }else {//与后面依次比较找比top小的然后替换
                Integer top = priorityQueue.peek();
                if(arr[i]<top){
                    priorityQueue.poll();
                    priorityQueue.offer(arr[i]);
                }
            }
        }
        int[]ret =new int[k];
        for (int i = 0; i <k; i++) {
            int val=priorityQueue.poll();
            ret[i]=val;
        }
        return ret;
    }
}
